package com.wenhao.leetcode.medium;

import java.util.*;

/**
 * 题目：https://leetcode-cn.com/problems/combination-sum-ii/
 *
 * 这一题是组合总和的简化版
 *
 * 每一个数字只可以使用一次
 *
 * @author Wenhao Tong
 * @create 2021-06-27 22:42
 */
public class LeetCode40 {

    public static void main(String[] args) {
        LeetCode40 leetCode40 = new LeetCode40();
        List<List<Integer>> lists = leetCode40.combinationSum2(new int[]{2,5,2,1,2}, 8);
        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 根据题意不是直接去重
//        Set<Integer> set = new HashSet<>();
//        for (int i : candidates) {
//            set.add(i);
//        }
//        Integer[] ints = new Integer[set.size()];
//        set.toArray(ints);
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();
        dfs(0,candidates,target, path);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();

    public void dfs (int index,int[] candidates,int target,List<Integer> path) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = index;i < candidates.length;i++) {
            // 如果当前的数字是重复的数字，那么直接看下一个数字
            // 重复的数字在递归中是会用到的，但是在递归内部的循环中一旦使用了就是重复的
            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (target - candidates[i] < 0) {
                break;
            }
            path.add(candidates[i]);
            dfs (i + 1,candidates,target - candidates[i],path);
            path.remove(path.size() - 1);
        }
    }
}
